package com.wang.utils.linklist;

/**
 * @author 10570
 * @date 2021/7/18 21:46
 */
public class CircleLinkedListDemo {
    /**
     * 约瑟夫问题
     * 1、环形链表
     *     （1）构建一个单向的环形链表思路
     *          a、先创建一个节点，让first指向该节点-并形成环形
     *          b、后面当没创建一个新的节点，就把节点加入到已有的环形链表中
     *      （2）遍历环形链表
     *          a、先让一个辅助指针变量指向first节点，
     *          b、然后通过一个while循环遍历环形链表，curboy.next = first
     */

    public static void main(String[] args) {
        CircleSingleLinkedList linkedList = new CircleSingleLinkedList();
        /*linkedList.addBoy(1);
        linkedList.addBoy(2);
        linkedList.addBoy(3);
        linkedList.addBoy(4);*/
        linkedList.addBoy(5);
        linkedList.listBoy();
        System.out.println("测试孩子出圈");
        linkedList.countBoy(1,2,5);
    }
}

//创建一个单向环形链表
class CircleSingleLinkedList{
    //创建一个first节点
    private Boy first = new Boy(-1);

    //添加节点，构建成环形链表
    public void addBoy(int nums){
        //判断
        if (nums <1 ){
            System.out.println("nums不正确");
            return;
        }
        Boy curBoy = null; //辅助指针
        for (int i = 1 ;i<= nums;i++){
            //根据编号创建节点
            Boy boy = new Boy(i);
            if (i == 1){
                first = boy;
                first.setNext(first);
                curBoy = first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    //遍历环形链表
    public void listBoy(){
        if (first == null){
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        //first不能动，使用一个辅助指针
        while (true){
            System.out.printf("孩子的编号%d\n",curBoy.getNo());
            if (curBoy.getNext() == first){
                System.out.println("遍历结束");
                break;
            }
            curBoy = curBoy.getNext();//后移
        }
    }

    //出圈编号
    /**
     * 根据用户输入，生成一个孩子出圈的顺序
     * 1、创建辅助指针helper，指向环形链表最后节点
     *      先移动到first和helper移动到key的位置
     * 2、孩子报数的时候，first和helper指针同时移动 m-1 次
     * 3、将first指向的孩子出圈
     *  first = first.next
     *  helper.next = first
     *  没有被引用就被垃圾回收
     */
    //计算出圈顺序

    /**
     *
     * @param startNo  从哪开始
     * @param countNum  数了几次
     * @param nums      最初孩子数
     */
    public void countBoy (int startNo,int countNum,int nums){
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误");
            return;
        }
        Boy helper = first;
        //完成出圈
        while (true){
            if (helper.getNext() == first){
                //指向了最后节点
                break;
            }
            helper  = helper.getNext();
        }
        //报数、定位
        for (int j = 0 ; j < startNo - 1 ; j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //移动后出圈循环操作--直到只有一个孩子的时候
        while (true){
            if (helper == first){
                //只剩一人
                break;
            }else {
//                first和helper移动countNum次
                for (int j = 0 ;j < countNum-1 ;j++){
                    first= first.getNext();
                    helper = helper.getNext();
                }
                System.out.printf("孩子的编号%d\n.000",first.getNo());
                //将该节点出圈
                first = first.getNext();
                helper.setNext(first);
            }
        }
        System.out.printf("最后留在圈中%d\n",first.getNo());

    }

}
//创建一个boy
class Boy{
    private int no;
    private Boy next ;  //指向下一个节点

    public Boy(int no, Boy next) {
        this.no = no;
        this.next = next;
    }

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}


